import java.util.Stack;

/**
 * @author by Urolain
 * @Classname Solution
 * @Description solution for Find the celebrity
 * @Date 2020/5/20 9:43
 */
public class Solution {


    /**
     * 从n个人中找出名人
     * @param n
     * @return
     */
    private int findCelebrity(int n) {
        // base case
        if (n <= 0) { return -1;}
        if ( n == 1) { return 0;}

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            stack.push(i);
        }

        int a = 0, b = 0;
        while (stack.size() > 1){
            a = stack.pop();
            b = stack.pop();
            if (knows(a,b)) {
                stack.push(b);
            } else {
                stack.push(a);
            }
        }

        //double check
        int c = stack.pop();
        for (int i = 0; i < n; i++) {
            if ( i != c && knows(c,i) || !knows(i,c)) {
                return -1;
            }
        }
        return c;
    }

    /**
     * 判断a是否认识b
     * @param a 人员1
     * @param b 人员2
     * @return true/false
     */
    private  boolean knows(int a, int b) {
        return Math.random()/2 == 0 ;
    }
}
